章節名稱: theory of generalization

一 Restriction of Break Point

繼續 Break Point

可先回顧一下上次的章節。

在知道 break point 後我們還能得知那些訊息呢？

假設 break point 在 k = 2 時，代表在 N = 2 時，它最多只會有 3 種組合。
依照此規則下去看 N = 3 時，其中任兩點都不能 shattered :

A B C
o o o
o x o
x o o
x x x

其中 A,B 完成了所有組合，所以是 shattered ，這樣就與 k = 2 矛盾了。

最多只會有 4 種組合。因為到第 5 種時必會有兩點 shattered ，而產生矛盾。

結論來說我們有了 break point 後，對於接下來的 N 都加上了限制，好像可以減少 $m_{\mathcal{H}}(N)$ 複雜度。

$m_{\mathcal{H}}(N)$ 在有了 break point 後，其最多能產生的組合數是不是多項式呢？如果是，我們就能說 $m_{\mathcal{H}}(N)$ 也是多項式了。

二 Bounding Function: Basic Cases

Bounding Function

Bounding Function: 結合前面講得 growth function 還有 break point(k)，它是 growth function 的上限，也就是在 N 個點，break point = k 的情況下最多所能做出的組合數，任意 k 個點都不能 shatter。以 $B(N,k)$ 來表示。

不管成長函數如何，都可以用它，例如: $B(N,3)$ 對 positive intervals(k = 3) 和 1D perceptrons(k = 3)，皆是上限。

下一個目標則是看看 Bounding Function 會不會小於等於多項式。

來試著建表:

• $B(N,1) = 1$，永遠都只有一種。
• $B(N,k) = 2^N$ for $N \lt k$，不管怎麼樣都不會到達 k 個點，也不會違反 break point 的限制。
• $B(N,k) = 2^k-1$ for $N = k$，在 k 個點時沒辦法 shattered ，剛好是 k 個點全部有幾組再減掉一組，即可滿足 break point 的限制。

小練習

如同前面所提 $m_{\mathcal{H}}(N)$ 是實際的成長函數，而 $B(N,k)$ 是其上限。